/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/regular-expression-matching
   @Language: C++
   @Datetime: 19-03-12 15:50
   */


// Method 1, DP, Time 50ms
class Solution {
public:
	/**
	 * @param s: A string 
	 * @param p: A string includes "." and "*"
	 * @return: A boolean
	 */
	bool isMatch(string &s, string &p) {
		// write your code here
		int n=s.length(), m=p.length();
		vector<vector<bool> > dp(n+1,vector<bool>(m+1,false));
		dp[0][0]=true;
		for(int i=0; i<=n; i++){
			for (int j=1; j<=m; j++){
				if (j>1 && p[j-1]=='*'){
					if (i>0) dp[i][j] = dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.');
					dp[i][j] = dp[i][j] || dp[i][j-2];
				}
				else if (i>0){
					dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
				}
			}
		}
		return dp[n][m];
	}
};

// Method 2, Recursion, Time 151ms
class Solution {
public:
	/**
	 * @param s: A string 
	 * @param p: A string includes "." and "*"
	 * @return: A boolean
	 */
	bool isMatch(string s, string p) {
		// write your code here
		if(p.empty()) return s.empty();
		if(p.length()>1 && p[1]=='*')
			return isMatch(s,p.substr(2)) ||
				(!s.empty() && (s[0]==p[0] || p[0]=='.') && isMatch(s.substr(1),p));
		else
			return !s.empty() && (s[0]==p[0]||p[0]=='.') && 
				isMatch(s.substr(1),p.substr(1));
	}
};

// Method 3, Regex, Time 255ms
#include <regex>
class Solution {
public:
	/**
	 * @param s: A string 
	 * @param p: A string includes "." and "*"
	 * @return: A boolean
	 */
	bool isMatch(string &s, string &p) {
		// write your code here
		if(p.length() && p[0]=='*') return false;
		string r;
		for(const auto &ch:p)
			if(ch=='.') r.append("[a-z,A-Z]{1}");
			else r.push_back(ch);
		return regex_match(s, regex(r));
	}
};
